package zuoshen.chapter1;

import java.util.Stack;

//用一个栈对另一个栈从顶到低从大到小排序
public class SortStackByStack {

    public static void main(String[] args) {

        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(5);
        stack.push(2);
        stack.push(4);
        stack.push(3);
        sortStack(stack);
        while (!stack.isEmpty()){
            System.out.print(stack.pop()+",");
        }
    }

    public static void sortStack(Stack<Integer> stack){
        Stack<Integer> aidStack = new Stack<>();
        //主要思想就是stack出栈到aidStack，同时满足aidStack从顶到底单减，如果不满足就把aidStack出栈到stack
        //这里要求aidStack单减是因为后面需要出栈到stack, stack是从顶到底单增的
        while (!stack.isEmpty()){
            int num = stack.pop();
            while (!aidStack.isEmpty()&&aidStack.peek()<num){
                stack.push(aidStack.pop());
            }
            aidStack.push(num);
        }
        while (!aidStack.isEmpty()){
            stack.push(aidStack.pop());
        }
    }
}
